package com.jiang.daily.Q1338;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/15 16:37
 */
class Solution {
    public int minSetSize(int[] arr) {
        // int len = arr.length;
        // HashMap<Integer, Integer> map = new HashMap<>();
        // for (int i = 0; i < len; i++) {
        //     map.compute(arr[i], (k, v) -> v == null ? 1 : v + 1);
        // }
        // map = map.entrySet().stream()
        //         .sorted(Map.Entry.comparingByValue((e1, e2) -> e2 - e1))
        //         .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
        // int res = 0;
        // for (int v: map.values()) {
        //     nowLen += v;
        //     res++;
        //     if (nowLen >= len / 2) return res;
        // }
        // return 0;

        int len = arr.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num: arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> list = new ArrayList<>(map.values());
        Collections.sort(list, Collections.reverseOrder());
        int res = 0, cnt = 0;
        for (int n: list) {
            cnt += n;
            res++;
            if (cnt * 2 >= len) break;
        }
        return res;

    }
}
